/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class MyBinarySTree<E extends Comparable<? super E>>{
    public TreeNode root;
    private int size;
    private int hight;
    private class TreeNode<E>{
        TreeNode left;
        TreeNode right;
        E value;
        public TreeNode(E value){
            this.value = value;
        }
    }
    public static <T extends Comparable<? super T>> MyBinarySTree buildTree(List<T> inorder,List<T> posOrder){
        MyBinarySTree<T> tree = new MyBinarySTree<>();
        tree.size = 0;
        tree.root=tree.build(inorder,posOrder);        
        return tree;
    }
    private TreeNode build(List<E> inOrder, List<E> posOrder){
        if(posOrder.isEmpty() || posOrder == null) return null;
        if(inOrder.isEmpty() || inOrder == null) return null;
        E e = posOrder.get(posOrder.size()-1);
        int index = inOrder.indexOf(e);
        TreeNode node = new TreeNode(e);
         List<E> subLeftinorder = inOrder.subList(0,index);
        List<E> subLeftposorder = posOrder.subList(0,index);
        node.left = build(subLeftinorder,subLeftposorder);
        List<E> subRightinorder = inOrder.subList(index+1,posOrder.size());
        List<E> subRightposorder = posOrder.subList(index,posOrder.size()-1);
         node.right = build(subRightinorder,subRightposorder);
        return node;
    }
    public List<List<E>> levelOrder(){
         List<List<E>> res = new ArrayList<>();
        if(root==null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int c = q.size();
           List<E> oneLL =new ArrayList<>();
            while(c>0){
                TreeNode p = q.remove();
                oneLL.add((E)p.value);
                c--;
                if(p.left!=null) q.add(p.left);
                if(p.right!=null) q.add(p.right);
            }
            res.add(oneLL);            
        }
        return res;
    }
}